// 1. 136-只出现一次的数字
// 2. 169-多数元素
// 3. 颜色分类
// 4. 下一个排序
// 5. 寻找重复数
// 6. 缺失的第一个挣数
// 7. 搜索插入位置
// 8. 搜索二维矩阵
// 9. 在排序数组中查找元素的第一个和最后一个位置
// 10. 搜索旋转排序数组
// 11. 寻找旋转排序素组中的最小值
// 12. 矩阵置零
// 13. 螺旋矩阵
// 14. 旋转图像
// 15. 搜索二维矩阵 II





// 1. 只出现一次的数字
// 题解：数组中只会出现一次的数字
// 思路：基本原理就是 两个相同数1^1 = 0
// 注意：注意初始值
var singleNumber = function (nums) {
    // 基本原理就是 两个相同数1^1 = 0
    let res = nums[0]
    for (let i = 1; i < nums.length; i++) {
        res = res ^ nums[i]
    }
    return res

};

// 2. 多数元素
// 题解：数量最多的元素
// 思路：对拼消耗，摩尔投票法
// 注意：初始化
var majorityElement = function (nums) {
    let count = 1;
    let majority = nums[0];

    for (let i = 1; i < nums.length; i++) {
        if (count === 0) {
            majority = nums[i]
        }

        if (majority === nums[i]) {
            count++
        } else {
            count--
        }
    }

    return majority
};


// 3. 颜色分类
// 题解：123 按顺序排列
// 思路：0 插最前 2插最后 记得移动i（因为移到最后，原目标元素到了下一位得记得--）
// 注意：unshift - 从头插 splice - 删除 并返回
var sortColors = function (nums) {
    let count = 0;
    let i = 0;

    while (count < nums.length) {
        const num = nums[i]
        if (num === 0) {
            nums.unshift(nums.splice(i, 1))
        } else if (num === 2) {
            nums.push(nums.splice(i, 1))
            i--
        }
        count++;
        i++
    }
};


// 4. 下一个排序
// 题解：
// 思路：
// 注意：
var nextPermutation = function(nums) {
    
    //  1.全数升序排列是最小的，全数逆序排列是最大的 （）
    //  2.第一个数字越大其字典序越大
    //  3.后面的数字升序排列比逆序排列小

    // 左边较小的数，右边较大的数
    // 规律就是： 从右到左先找到 第一个非递减（321）的较小数；再从右到左找到比这个较小数大的下一个数；两者替换； 然后把后面翻转，使其变大的幅度小一点
    // https://blog.csdn.net/m0_63988748/article/details/125598526
    let i = nums.length - 2;
    while(i>=0 && nums[i] >= nums[i+1]){
        i--
    }
    // 找到较小数与较大数，两者替换
    if(i>=0){
        let j = nums.length -1;
        while(j >=0 && nums[j] <= nums[i]){
            j--
        }
        [nums[i], nums[j]] = [nums[j], nums[i]]
    }
    // 后面的两则替换
    let l = i + 1;
    let r = nums.length - 1;
    while(l < r){
        [nums[l], nums[r]] = [nums[r],nums[l]]
        l++;
        r--;
    }
};



// 5. 寻找重复数
// 题解：找到出现多次的数  cycle sort
// 思路：用值做索引，将每个值交换到对应的索引位置，当再次出现索引与值相等的情况则就是目标值
// 注意：数字范围在1-n不会出现第一位就是0的情况
var findDuplicate = function (nums) {
    while (true) {
        let index = nums[0]
        if (nums[index] === nums[0]) {
            return nums[0]
        } else {
            // [nums[0], nums[index]] = [nums[index], nums[0]]
            const temp = nums[nums[0]]; // 交换
            nums[nums[0]] = nums[0];
            nums[0] = temp;
        }
    }
};

// 6. 缺失的第一个挣数
var firstMissingPositive = function (nums) {
    for (let i = 0; i < nums.length; i++) {
        while (
            nums[i] >= 1 &&
            nums[i] <= nums.length &&     // 对1~nums.length范围内的元素进行安排
            nums[nums[i] - 1] !== nums[i] // 已经出现在理想位置的，就不用交换
        ) {
            const temp = nums[nums[i] - 1]; // 交换
            nums[nums[i] - 1] = nums[i];
            nums[i] = temp;
        }
    }
  // 现在期待的是 [1,2,3,...]，如果遍历到不是放着该放的元素
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] != i + 1) {
            return i + 1
        }
    }

    return nums.length + 1 // 发现元素 1~nums.length 占满了数组，一个没缺
};
console.log(firstMissingPositive([3, 4, -1, 1]))

// 7. 搜索插入位置
// 题解：
// 思路：
// 注意：
var searchInsert = function(nums, target) {
    let left = 0;
    let right = nums.length -1;
    while(left <= right){
        let mid = Math.floor((left+ right) / 2)
        if(nums[mid] === target){
            return mid
        } else if(nums[mid] < target){
            left = mid + 1
        } else {
            right = mid -1
        }
    }
    return left
};

// 8. 搜索二维矩阵
// 题解：
// 思路：若将矩阵每一行拼接在上一行的末尾，则会得到一个升序数组，我们可以在该数组上二分找到目标元素。
// 注意：
var searchMatrix = function(matrix, target) {
    const m = matrix.length;
    const n = matrix[0].length
    let left = 0;
    let right = m*n -1;

    while(left <= right){
        const mid = Math.floor((right - left)/2)+left
        const x = matrix[Math.floor(mid/n)][mid % n]
        if(x < target){
            left = mid + 1
        } else if(x > target) {
            right = mid -1
        } else {
            return true
        }
    }
    return  false
};

// 9. 在排序数组中查找元素的第一个和最后一个位置
// 题解：
// 思路：
// 注意：
var searchRange = function(nums, target) {
    let res = [-1, -1]
    let left = 0;
    let right = nums.length - 1;

    // 找右边界 target 为数组的最后一个值，或者 target 右边的元素不等于 8
    while(left <= right){
        let mid = left + Math.floor((right - left) / 2 )

        if(nums[mid] === target && (mid === nums.length -1 || nums[mid + 1] > target)){
            res[1] = mid;
            break
        }
        if(nums[mid] <= target){
            left = mid +1
        }else {
            right = mid - 1
        }
    }

    // 找左边界 target 为数组的第一个值，或者 target 左边的元素不等于 8
    left = 0; // 之前可能变过，要复原
    while(left <= right){
        let mid = left + Math.floor((right - left) / 2 )
        if(nums[mid] === target && (mid === 0 || nums[mid - 1] < target)){
            res[0] = mid;
            break
        }
        if(nums[mid] >= target){
            right = mid - 1
        }else {
            left = mid +1
        }
    }

    return (res[0]=== -1 || res[1] === -1) ? [-1, -1]: res
};

// 10. 搜索旋转排序数组
// 题解：
// 思路：
// 注意：
var search = function(nums, target) {
    let left = 0;
    let right = nums.length -1;
    
    while(left <= right){
        let mid = left + Math.floor((right - left)/2)
        if(nums[mid] === target){
            return mid
        } 
        // 判断左右序列属性
        if(nums[mid]> nums[right]){
            // 左侧升序，右侧旋转
            // 判断target在升序， 还是在循环数组里
            if(nums[mid] > target && nums[left] <= target){
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            // 左侧旋转，右侧升序
            // 判断target在升序， 还是在循环数组里
            if(nums[mid] < target && nums[right] >= target){
                left = mid + 1
            } else {
                right = mid -1
            }
        }
    }
    return -1
};

// 11. 寻找旋转排序素组中的最小值
// 题解：
// 思路：
// 注意：
var findMin = function(nums) {
    let left = 0;
    let right = nums.length -1;

    while(left <= right){
        if(nums[left] <= nums[right]){
            // 是一个递增数组
            return nums[left]
        }

        let mid = left + Math.floor((right - left)/2)
        // 找升序
        if(nums[mid] > nums[right]){
            // 左升，右循环
            left = mid+1 // mid已经比最右侧大了，肯定不是最小值 +1
        } else {
            // 左循环，右升
            right = mid // 要包含mid mid可能是最小值
        }
    }

    return -1
};


// 12.矩阵置零
var setZeroes = function(matrix) {
    let m = matrix.length;
    let n = matrix[0].length;
    const row = new Array(m).fill(false);
    const col = new Array(n).fill(false);

    for(let i =0; i< m;i++){
        for(let j=0; j< n; j++){
            if(matrix[i][j] === 0){
                row[i] = col[j] = true
            }
        }
    }

    for(let i =0; i< m; i++){
        for(let j = 0; j< n; j++){
            if(row[i] || col[j]){
                matrix[i][j] = 0
            }
        }
    }

};

// 13.螺旋矩阵
var spiralOrder = function(matrix) {
    if(matrix.length === 0) return [];
    const res = [];

    let top = 0;
    let bottom = matrix.length - 1;
    let left = 0;
    let right = matrix[0].length - 1;

    while(top < bottom && left < right){
        for(let i = left; i< right; i++) res.push(matrix[top][i]) // 上
        for(let i = top; i< bottom; i++) res.push(matrix[i][right]) // 右
        for(let i = right; i> left; i--) res.push(matrix[bottom][i]) // 下
        for(let i = bottom; i > top; i--) res.push(matrix[i][left]) // 左
        right--
        top++
        bottom--
        left++ // 边界收缩
    }
    if(top === bottom){ // 剩下一行，从左到右依次添加
        for(let i = left; i<= right; i++){
            res.push(matrix[top][i]) 
        }
    } else if (left === right){ // 剩下一列 从上到下依次添加
        for(let i = top; i <= bottom; i++){
            res.push(matrix[i][left])
        }
    }
    return res
};

// 14.旋转图像
var rotate = function(matrix) {
    const n = matrix.length
    for(let i = 0; i< Math.floor(n/2); i++){
        for(let j =0; j < Math.floor((n+1)/2); j++){
            const temp = matrix[i][j];
            matrix[i][j] = matrix[n-j -1][i];
            matrix[n-j-1][i] = matrix[n-i-1][n-j-1]
            matrix[n-i-1][n-j-1]= matrix[j][n-i-1]
            matrix[j][n-i-1]= temp
        }
    }
    return matrix

};


// 15.搜索二维矩阵 II
var searchMatrix = function(matrix, target) {
    for(const row of matrix){
        const index = search(row, target)
        if(index >= 0 ) return true
    }
    return false
};

const search = (nums, target) => {
    let low = 0;
    let high = nums.length - 1;
    while(low <= high) {
        const mid = Math.floor((high - low)/2) + low;
        const num = nums[mid]
        if(num === target){
             return  mid
        } else if(num > target){
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return -1

}